Communications networks may carry data from a source to a destination along one or more paths. Some of these paths may include fewer intermediate stops (referred to as “hops”), and may therefore be shorter than others. For example, a path that goes directly from a source to a destination is referred to as a “1-hop path.” A 1-hop path may carry data to the destination faster or more efficiently than a 2-hop path, which is a path that includes a single intermediate device between the source and the destination. A path may include any number of hops.
Conventionally, available paths in the network between a source and a destination may be considered to determine which paths should be used to route data from the source to the destination. This may be accomplished by marking the paths with the fewest number of hops as the “best paths,” and then routing data over the designated best paths. There may be more than one best path over which data is routed, if multiple paths tie for the fewest number of hops. The amount of data provided to each of the best paths may be balanced so that one best path does not become saturated before another.
Equal-cost multi-path routing (ECMP) is an example of such a routing strategy, an example of which is described with reference to the exemplary network depicted in FIG. 6. As shown in FIG. 6, a network 600 includes a first host 610, a second host 620, a third host 630, and a fourth host 640. Each host is associated with a nearby switch 612, 622, 632, 642 which forwards data in the form of packets from one host to another. Each switch may connect to another switch using an egress port, such as the egress ports 614, 616 of switch 612 (both of which connect switch 612 directly to switch 632).
In the example shown in FIG. 6, two paths 615, 617 are available that directly connect the first switch 612 to the third switch 632. The equal-cost multi path routing strategy divides traffic bound from the first switch 612 to the third switch 632 between the two 1-hop paths 615, 617. Thus, traffic in the network 600 may be load-balanced among multiple paths, potentially increasing bandwidth in the network over as situation in which only a single best path is used.